package com.example.demo.leetcode.zuocheng.graph;

/**
 *
 * 在 1-N 范围内，机器人从 M 开始， 走到P ， 必须走 K 步， 有多少种走法
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/7/18 12:40
 */
public class Arr_机器人 {


    public static int process(int n ,int curr, int rest , int p){

        if(curr == p && rest == 0){
            return 1;
        }

        if(rest < 1){
            return 0;
        }

        int left = 0;
        //往左
        if(curr > 1){
            left = process(n,curr - 1 ,rest-1,p);
        }
        //往右
        int right = 0;
        if(curr < n){
            right = process(n,curr+1,rest-1,p);
        }
        return left + right;

    }


    //动态规划 - 记忆化搜索

    public static int walk(int n ,int curr, int rest , int p){

        int [][] dp = new int[n+1][rest+1];
        for(int i =0;i<=n;i++){
            for(int j=0;j<=rest;j++){
                dp[i][j]=-1;
            }
        }
        return processCache(n,curr,rest,p,dp);
    }


    public static int processCache(int n ,int curr, int rest , int p ,int [][] dp){

        if(dp[curr][rest] != -1){
            return dp[curr][rest];
        }

        if(curr == p && rest == 0){
            dp[curr][rest] = 1;
            return 1;
        }

        if(rest < 1){
            dp[curr][rest] = 0;
            return 0;
        }

        int left = 0;
        //往左
        if(curr > 1){
            left = processCache(n,curr - 1 ,rest-1,p,dp);
        }
        //往右
        int right = 0;
        if(curr < n){
            right = processCache(n,curr+1,rest-1,p,dp);
        }
        dp[curr][rest] = left + right;
        return left + right;
    }



    public static void main(String[] args) {

        System.out.println(process(7,3,3,2));
        System.out.println(walk(7,2,5,3));

    }


}
